package 动态规划.路径问题;

/**
 * @Date 2024/9/27 22:45
 * @description: 不同路径2
 * .    https://leetcode.cn/problems/unique-paths-ii/description/
 * @Author LittleNight
 */
public class likou63 {

    // 动态规划
    // 是不同路径1 的升级版: https://leetcode.cn/problems/unique-paths/
    public int uniquePathsWithObstacles(int[][] ob) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = ob.length, n = ob[0].length;
        int[][] dp = new int[m + 1][n + 1]; // 多开一个空间. 一行一列
        dp[0][1] = 1; // 根据题意, 至少有一个格子. 肯定有答案
        // 填表.
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                // 只要不是障碍物就可以.  是障碍物的话默认就是 0, 不用写
                // 注意和原始数组的下标映射
                if(ob[i - 1][j - 1] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }



}
